BM12 单链表的排序

https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08

最简单的做法：

func sortInList( head *ListNode ) *ListNode {
    var tmp []int
    for head != nil {
        tmp = append(tmp, head.Val)
        head = head.Next
    }
    
    sort.Ints(tmp)
    
    dump :=  &ListNode{}
    head = dump
    for i := 0; i < len(tmp); i++ {
        dump.Next = &ListNode{ Val: tmp[i] }
        dump = dump.Next
    }
    return head.Next
}

使用归并排序

func sortInList( head *ListNode ) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    fast, slow := head.Next, head
    // 通过快慢指针找到链表的中点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    tmp := slow.Next
    slow.Next = nil // 切断连接
    // 递归左右两边进行排序
    left := sortInList(head)
    right := sortInList(tmp)
    // 创建新的链表
    h := &ListNode{}
    res := h
    // 合并新的链表
    for left != nil && right != nil {
        if left.Val < right.Val {
            h.Next = left
            left = left.Next
        } else {
            h.Next = right
            right = right.Next
        }
        h = h.Next
    }
    // 因为最后剩余了一个节点可能在 left 或者 right 里面
    if left != nil {
        h.Next = left
    } else {
        h.Next = right
    }
    
    return res.Next
}